#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<int>& num){
        int length = num.size();
        int right_max = 0, jumps = 0;
        if(length == 1){
            return 0;
        }
        for(int i = 0; i != length; i++){
            right_max = max(right_max, i+num[i]);
            if(right_max >= length-1){
                jumps++;
                length = i+1;
                right_max = 0;
                i = -1;
            }
            if(length == 1){
                break;
            }
        }
        return jumps;
    }

    int ans2(vector<int>& num){
        int length = num.size();
        int step = 0, end = 0, right_max = 0;
        for(int i = 0; i < length-1; i++){
            if(right_max >= i){
                right_max = max(right_max, i+num[i]);
                if(i == end){
                    end = right_max;
                    step++;
                }
            }
        }
        return step;
    }

    //my ans 8ms
    int ans3(vector<int>& num){
        int length = num.size();
        int i = 0, p, next_p;
        int max_step;
        int step_num = 0;
        while(i < length-1){
            max_step = i + num[i];
            p = max_step;
            if(max_step >= length-1){
                step_num++;
                break;
            }
            while(p > i){
                if(p + num[p] > max_step){
                    max_step = p + num[p];
                    next_p = p;
                }
                p--;
            }
            step_num++;
            i = next_p;
        }
        return step_num;
    }

};

void test1(){
    vector<int> num = {2, 3, 1, 1, 4};

    Solution s;
    // int ret = s.ans1(num);
    // int ret = s.ans2(num);
    int ret = s.ans3(num);
    cout << ret << endl;
}

void test2(){
    vector<int> num = {0};

    Solution s;
    // int ret = s.ans1(num);
    // int ret = s.ans2(num);
    int ret = s.ans3(num);
    cout << ret << endl;
}

void test3(){
    vector<int> num = {2, 3, 0, 1, 4};

    Solution s;
    // int ret = s.ans1(num);
    // int ret = s.ans2(num);
    int ret = s.ans3(num);
    cout << ret << endl;
}

void test4(){
    vector<int> num = {5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0};

    Solution s;
    // int ret = s.ans1(num);
    // int ret = s.ans2(num);
    int ret = s.ans3(num);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();
    test4();

    return 0;
}